The present invention relates to a communications network for sending messages between a plurality of nodes having unique identities, said network comprising a server unit. The invention also relates to methods of routing messages within a communications network.
For example in the field of packet switched networks, information packets are routed from a sending node via a number of intermediate nodes to a receiving node. The basic problem for this operation, is that of minimising the length of the path between the sending and receiving nodes, i.e. the shortest path problem. The theoretically optimal solution to the problem is known as Djikstra""s algorithm. However, this is an ideal mathematical solution that cannot be implemented in its theoretical form.
Prior art solutions may involve the use of distributed routing tree information, where each node is provided with a routing tree that represents the shortest path to all connected nodes, see U.S. Pat. No. 4,987,536. Other solutions may include a central route determining node, see U.S. Pat. No. 5,608,721. The prior art solutions are not very cost-efficient,
One object of the invention is to find the shortest path from an arbitrary node to another arbitrary node in a uni- or bi-directional network with a minimum of stored information in each node.
For this object, the communications network according to the invention is characterized in that each node is provided with; first storing means for storing a list of all nodes neighbouring said node, which are directed to it, second storing means containing a data field for registration of identity of one node, and that a third storing means is provided in the central unit for forming a temporary queue.
In a particular embodiment of the communications network, the data field of the second storing means forms an array of cells which is indexed for all nodes in the network, said array being sized in proportion to the number of nodes in the network and wherein each cell is arranged to contain the identity of one node.
An advantageous embodiment of the invention, the distance between each pair of nodes is represented by a number of assumed virtual nodes, wherein said number is proportional to said distance.
Alternatively, the traffic load between two nodes is represented by a number of assumed virtual nodes, wherein said number is proportional to said traffic load.
A method of routing messages within a communications network for sending messages between a plurality of nodes having unique identities, for calculation of the shortest path between a first node and a second node is characterized in the steps of forming a list of the identities of all nodes neighbouring said first node and to which it is directed, putting the identity of the second node in a queue, writing a stop command in a data field for registration of identity of the second node, taking the identity of the node in front of the queue and writing its identity in the data field of all its neighbours, unless there already is an entry in this data field, putting the identity of a node in the queue each time an entry is written into the data field of this node, removing from the queue the identity of the node in front of the queue, after visiting all nodes in the list of all neighbouring nodes of said node, and repeating the step of taking the identity of the node in front of the queue and writing its identity in the data field of all its neighbours, until the visited node is the first node.
Advantageously, the network is checked for nodes which have been disconnected from a certain node.
Preferably, said checking comprises the steps of putting the identity of said node (n) in the queue and marking said node, taking the node in front of the queue and marking its unmarked neighbours, each time the identity of a new node is marked, it is placed in the queue, after visiting all nodes in the list of the identities of all nodes neighbouring said node in front of the queue, said node is removed from the queue and put in a set, repeating the step of taking the node in front of the queue and marking its unmarked neighbours until the queue is empty, and subtracting the resulting set from the set of all nodes which said node is aware of, wherein the result is the set of nodes which are disconnected from the aforementioned node.
A method of routing messages within a communications network for sending messages between a plurality of nodes having unique identities, for calculation of the shortest path between all pairs of nodes in the network is characterized in the steps of; forming a list of the identities of all nodes neighbouring a node and to which it is directed, putting the identity of the node in a queue, writing a stop command for this node in an array data field indexed for registration of identity of all nodes in the network, taking the identity of the node in front of the queue and writing its identity in the data field of all its neighbours, unless there already is an entry in this data field, putting the identity of the visited node in the queue each time an entry is written into the date field of a node, removing from the queue the identity of the nods in front of the queue, after visiting all nodes in the list of all neighbouring nodes of said node, repeating the step of taking the identity of the node in front of the queue and writing its identity in the data field of all its neighbours, until the queue is empty, and repeating the above step for all nodes in the network.
Advantageously, the network is checked if a node has connection to all other nodes.
Preferably, said checking comprises the steps of putting the identity of said node in the queue and marking said node, taking the node in front of the queue and marking its unmarked neighbours, each time the identity of a new node is marked, it is placed in the queue, after visiting all nodes in the list of the identities of all nodes neighbouring said node in front of the queue, said node is removed from the queue and put in a set, repeating the step of taking the node in front of the queue and marking its unmarked neighbours until the queue is empty, and subtracting the resulting set from the set of all nodes which said node is aware of, wherein the result is the set of nodes which are disconnected nodes.